1. Field
The disclosure relates to a method, system, and article of manufacture for preventing deadlocks.
2. Background
A set of threads may be referred to as being deadlocked if each thread in the set waits for an event that only another thread in the set can cause. When a plurality of threads race for a plurality of locks, deadlock conditions may exist. Certain implementations include special mechanisms, such as mechanisms to gain the locks in a specific order, that can prevent deadlock conditions from occurring. However, such mechanisms can be impractical to employ in certain situations.
Fine grained locks allow for high concurrency, making such fine grained locks a requirement for many highly scalable systems. However, fine grained locks may be difficult to use because of the danger of the occurrence of deadlocks. Certain implementations provide ways to ensure that deadlocks are avoided, but such implementations may put restrictions on how or in what order locks can be achieved, or may require complex try-and-backoff implementations.
One mechanism to prevent deadlock is to define an order in which locks are to be attempted by threads. Any thread can acquire as many of the locks as the thread desires, provided that the thread always acquire in the defined order. This prevents deadlock because it removes the circular wait condition for deadlock. Each thread, if the thread happens to block, is blocking on some other thread which is continuing processing. Ordering mechanisms work well if a thread is aware of the locks that are going to be needed ahead of time, and can acquire the locks in the right order. Ordering mechanisms fail if it is impossible or inconvenient to acquire the locks in the right order.
In try-and-backoff implementations a thread makes a non-blocking attempt on a lock. If the lock is available, the thread acquires it immediately and continues on; if not, then the thread is returned an error. Anytime the thread fails a “try,” the thread rewinds itself, unlocking any locks that the thread already has, and then starts over. This prevents deadlock because it removes the hold and wait condition. A system can be devised with a thread that never blocks while holding another lock.
Sometimes, ordering mechanisms are combined with try-and-backoff implementations. The system is allowed to acquire the locks in any order, and blocking lock operations can be used whenever locks are being gained in order. However, a thread uses “try” (i.e., a non blocking lock attempt) anytime that that the thread attempts a lock that is out of order. If the thread fails a “try”, then the thread unwinds, releases all of the locks that the thread had gained, and tries again. Sometimes, on the second pass it is possible to gain the locks in the right order, and thus use blocking operations throughout.
Try-and-backoff works well a thread is able to unlock locks if one fails. However, this is often not the case; often, threads perform operations which are hard to undo, and it may be impractical to release all of the locks if one lock fails.
In certain implementations, the locking procedure is made into a critical section. Such implementations use a lock to ensure that there is only one thread performing locks at any given time. A process using such an implementation would perform its work as follows:
1. Lock the lock-attempt-lock;
2. Gain various data locks;
3. Unlock the lock-attempt-lock;
4. Perform work; and
5. Unlock the data locks.
Such implementations prevents deadlock, since there is only one process performing locks at any given moment. It allows for fine grained data locks, which means that there can be a lot of concurrency in data access. Moreover, if it so happens that there is not much contention for these data locks, then the system will have high efficiency. Threads will only hold the lock-attempt-lock for short periods, so there will be little contention. However, such implementations do cause serious contention in some circumstances. If a thread gains the lock-attempt-lock and then immediately blocks on some other lock, then no other thread will be able to gain any locks in the system until the data lock becomes available. In the worst case, this means that the interaction of two threads (a first thread, which holds the data lock for a long time, and a second thread, which blocks on the lock) can stop all future threads from gaining any locks.